两个数组的交集 II-简单

难度：简单

题目描述：
给定两个数组，编写一个函数来计算它们的交集。

示例：

输入: (nums1 = [1, 2, 2, 1]), (nums2 = [2, 2]);
输出: [2, 2];

1
2

解题思路：
暴力解法，遍历短数组，查询元素在长数组中 index 值，如果存在则找到交集，并从长数组中删除该元素

var intersect = function (nums1, nums2) {
  let short = [];
  let lang = [];
  let x = [];
  if (nums1.length > nums2.length) {
    short = nums2;
    lang = nums1;
  } else {
    short = nums1;
    lang = nums2;
  }
  for (let i = 0; i < short.length; i++) {
    let index = lang.indexOf(short[i]);
    if (index !== -1) {
      lang.splice(index, 1);
      x.push(short[i]);
    }
  }
  return x;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

哈希表
先用 Hashmap 记录第一个数组中的元素【放在 key】，和出现的次数【放在 value】。

然后再遍历第二个数组，如果找到对应元素，则添加这个元素到返回数组里。

如果 value 值大于 1，HashMap 中的 value 值减 1，表示已经找到一个相同的了。

如果 value 值等于 1，则删除该元素

var intersect = function (nums1, nums2) {
  let hash = new Map();
  let res = [];
  for (let i = 0; i < nums1.length; i++) {
    if (hash.has(nums1[i])) {
      hash.set(nums1[i], hash.get(nums1[i]) + 1);
    } else {
      hash.set(nums1[i], 1);
    }
  }

  for (let i = 0; i < nums2.length; i++) {
    let temp = nums2[i];
    let hashKey = hash.get(temp);
    if (hash.has(temp)) {
      res.push(temp);
      if (hashKey > 1) {
        hash.set(temp, hashKey - 1);
      } else {
        hash.delete(temp);
      }
    }
  }

  return res;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

两个数组排序
设定两个为 0 的指针，比较两个指针的元素是否相等
如果相等，元素 push 到返回值里，两个指针同时往前
如果不相等，元素小的指针往前

var intersect = function (nums1, nums2) {
  let p1 = 0;
  let p2 = 0;
  let res = [];
  nums1 = nums1.sort((a, b) => a - b);
  nums2 = nums2.sort((a, b) => a - b);
  while (p1 < nums1.length && p2 < nums2.length) {
    if (nums1[p1] == nums2[p2]) {
      res.push(nums1[p1]);
      p1++;
      p2++;
    } else if (nums1[p1] < nums2[p2]) {
      p1++;
    } else {
      p2++;
    }
  }
  return res;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

← 字符串中的第一个唯一字符-简单存在重复元素 III-中等 →

# 两个数组的交集 II-简单

两个数组的交集 II-简单